class Solution {
    private static long ans = Long.MAX_VALUE;

    public static int minimumTimeRequired(int[] jobs, int k) {
        ans = Long.MAX_VALUE;
        // 每个工人的时间数组
        long[] times = new long[k];
        dfs(jobs, times, 0, 0L);
        return (int) ans;
    }

    /**
     * @param jobs
     * @param times   每个工人的时间数组
     * @param index   现在分配第index项工作
     * @param maxTime 所有工人的最大时间，我们要求这个时间尽可能小
     */
    private static void dfs(int[] jobs, long[] times, int index, long maxTime) {
        if (index == jobs.length) {
            ans = Math.min(maxTime, ans);
            return;
        }
        for (int i = 0; i < times.length; i++) {
            // 因为分配时要求每个工人必须有工作，所以我们要求从左到右给工人分配的时候，不允许"前面一个没有值，后面一个有值"的情况
            // 为什么可以这样规定？因为工人的顺序是对结果没有影响的，也就是顺序可以调换
            if (i != 0 && times[i - 1] == 0L) {
                return;
            }
            // 将时间尝试分配给每个工人
            times[i] += (long) jobs[index];
            long tmpMax = Math.max(maxTime, times[i]);
            // 如果当前的时间已经大于之前算过的结果，抛弃掉，只保留更小的时间
            if (tmpMax < ans) {
                dfs(jobs, times, index + 1, tmpMax);
            }
            // 回溯，将时间退还出来，这样就可以给下一个工人
            times[i] -= (long) jobs[index];
        }
    }
}
